package com.example.graph;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 * <p>
 * 提示：
 * 0 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 */
public class Leetcode128_LongestConsecutive {
    public static void main(String[] args) {
//        int[] nums = {100, 4, 200, 1, 3, 2};
//        int[] nums = {1,2,0,1};
        int[] nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        System.out.println(new Solution().longestConsecutive(nums));

    }


    static class Solution {

        public int longestConsecutive(int[] nums) {
            return longestConsecutive2(nums);
        }

        /**
         * 解法二:hash表
         * 先将数组转化成HashSet(去重)
         * 然后遍历set
         *     方式一:
         *        枚举当前元素的+1,+2 ... 看set里面是否存在并更新连续序列的长度
         *
         *     方式二:
         *        先判断当前元素 -1 在不在set里面，
         *        如果存在则跳过(避免重复搜索)，不在再去判断+1, +2是否存在，并更新连续序列的长度
         * @param nums
         * @return
         */
        private int longestConsecutive2(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int maxLen = 1;
            Set<Integer> numSet = new HashSet<>();
            // 将数据放入set中去重
            for (int num : nums) {
                numSet.add(num);
            }

            for (Integer num : numSet) {
                if (!numSet.contains(num - 1)) {
                    int tmp = num + 1;
                    int count = 1;
                    while (numSet.contains(tmp)) {
                        count++;
                        tmp++;
                    }
                    maxLen = Math.max(maxLen, count);
                }
            }

            return maxLen;
        }

        /**
         * 解法一:暴力法
         * 先将数组排序
         * 然后依次比较当前和上一个元素是否相差1
         * @param nums
         * @return
         */
        private int longestConsecutive1(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int maxLen = 1;
            Arrays.sort(nums);

            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if ((nums[i] - nums[i - 1]) == 1) {
                    maxLen = Math.max(maxLen, ++count);
                } else if ((nums[i] - nums[i - 1]) == 0){ // 跳过相同的元素
                    continue;
                } else {
                    count = 1;
                }
            }
            return maxLen;
        }
    }
}
